\documentclass[10pt]{article}
\usepackage{amsmath}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\newcommand{\problem}[2][No]{\noindent{\sc Problem #1.} #2}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\answer}[1]{\noindent{\sc Answer. }#1}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\reference}{\noindent{\sc Reference. }}

\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}
\newcommand{\BigO}{\mathcal{O}}

\begin{document}

\problem[168]{Number Rotations.}

Consider the number 142857. We can right-rotate this number by moving the last digit (7) to the front of it, giving us 714285.
It can be verified that $714285=5 \times 142857$.

This demonstrates an unusual property of 142857: it is a divisor of its right-rotation.

Find the last 5 digits of the sum of all integers $n, 10 < n < 10^{100}$, that have this property.

\solution

%We use a semi-brute-force algorithm that enumerates all numbers with this property. 
Write a $k$-digit positive integer $n$ as
\begin{equation}
n = a_{k-1} \times 10^{k-1} + \cdots + a_1 \times 10 + a_0 \label{eq:eq1}
\end{equation}
where $0 \le a_i \le 9$ for $0 \le i < k-1$, and $1 \le a_{k-1} \le 9$.

Let $R(n)$ denote the right rotation of $n$, then
\begin{equation}
R(n) = a_0 \times 10^{k-1} + \cdots + a_2 \times 10 + a_1 \label{eq:eq2}
\end{equation}

Suppose $n$ divides $R(n)$. Let $m = R(n)/n$. 
%Obviously $1 \le m \le 9$. 
It follows that 
\begin{equation}
R(n)= mn = (m a_{k-1}) \times 10^{k-1} + \cdots + (m a_1) \times 10 + ma_0 \label{eq:eq3}
\end{equation}

Now put equation \eqref{eq:eq2} and \eqref{eq:eq3} together, and work out the coefficients $a_i$ from the last digit backwards. Comparing the last digit of $R(n)$, we have
\[
a_1 \equiv m a_0 \,\, (\text{mod } 10)
\]
Let $c_1 = \lfloor m a_0 / 10 \rfloor$, i.e. the \emph{carry} from multiplying the last digit of $n$ by $m$. Subtract $a_1$ from equation \eqref{eq:eq2} and \eqref{eq:eq3} and divide both equations by 10, and we find
\[
a_2 \equiv m a_1 + c_1 \,\, (\text{mod } 10)
\]
This process can be continued by defining $c_i = \lfloor m a_{i-1} / 10 \rfloor$ (note that $c_0=0$) and solving
\[
a_i \equiv m a_{i-1} + c_{i-1} \,\, (\text{mod } 10)
\]
until we reach the left-most digit of $R(n)$, where
\[
a_0 = m a_{k-1} + c_{k-1} .
\]

The algorithm is outlined as follows. Obviously $1 \le a_0 \le 9$ and $1 \le m \le 9$. We enumerate every combination of $a_0$ and $m$. For each given $a_0$ and $m$, we run the above procedure to find the smallest $k$ where $a_0 = m a_{k-1} + c_{k-1}$. The number $n$ found this way is the smallest number with this property that ends with $a_0$ and with multiplier $m$. 

Once we find such an $n$ (with $k$ digits), we can generate a family of numbers with this property from it, by concatenating multiple $n$s together. That is, we find
\[
n, n+n \times 10^k, n+n \times 10^k + n \times 10^{2k}, \ldots
\]
all with this property. Suppose the maximum number requested has $K$ digits, then there are $l=\lfloor K/k \rfloor$ terms in the above sequence. Their sum is 
\begin{align}
S(n) 
&= n \times \left[ 1 + (1+10^k) + \cdots + (1+10^k+\cdots+10^{(l-1)k}) \right] \notag \\
&= n \times \left[ l + (l-1) \cdot 10^k + (l-2) \cdot 10^{2k} + \cdots + 10^{(l-1)k} \right] \notag
\end{align}
We can then find $S(n)$ modulo $10^M$ easily.

Note: the single digit number 1 through 9 also satisfy the property. They should be excluded from the final sum.

\answer{59206}

\complexity

Time complexity: $\BigO(B^2 MN)$, where $B$ is the base of the number (10 in this problem), $M$ is the number of digits in the modulo (5 in this case), and $N$ is the number of digits in the upper bound (100 in this case).

Space complexity: $\BigO(1)$

\end{document} 